/*
	MIDAS Context Based Routing
	cbr_crtable.cc
	Copyright (c) 2007 Radoslaw Olgierd Schoeneich
	MEAG IT PW
*/

#include <map>

#include <semaphore.h>

#include "scheduler.h"

#include "cbr_crtable.h"
#include "cbr_config.h"

sem_t crtable_sem;

/**
 * CBR route constructor.
 *
 * @param tr reference to CBR triple
 * @param forwarder CBR id of the forwarding node
 *
 * Adds new route described by the CBR triple @a tr (concept,
 * source and hop count) and the forwarding node id @a forwarder.
 *
 * Route lifetime equals CTX_ROUTE_LIFE.
 */

cbr_Route::cbr_Route(const cbr_Triple& tr, cbr_ID forwarder)
{
	this->concept = tr.getConcept();
	this->expire = sclock() + CTX_ROUTE_LIFE;
	this->source = tr.getSource();
	this->forwarder = forwarder;
	this->hop_count = tr.getMetric() + 1;
}

/**
 * Update CBR route.
 *
 * @param tr reference to CBR triple
 * @param forwarder CBR id of the forwarding node
 *
 * Updates existing route described by the CBR triple @a tr (concept,
 * source and hop count) and the forwarding node id @a forwarder.
 *
 * Hop count is updated only if it the value is smaller than
 * the previous one.
 *
 * @todo
 * - Why it is not updated unconditionally? CTX_ROUTE_LIFE
 *   is bigger than HELLO_INTERVAL so this looks like a bug.
 *
 * @return "true" on success, "false" otherwise.
 */

bool cbr_Route::update(const cbr_Triple& tr, cbr_ID forwarder)
{
	if (concept != tr.getConcept() || source != tr.getSource()
					|| this->forwarder != forwarder)
		return false;

	// reset expiry time
	expire = CTX_ROUTE_LIFE;

	if (tr.getMetric() + 1 < this->hop_count)
		this->hop_count = tr.getMetric() + 1;

	return true;
}

/**
 * Get route as CBR triple.
 */

cbr_Triple* cbr_Route::getAsTriple() const
{
	return new cbr_Triple(concept, hop_count, source);
}

/**
 * CBR routes table constructor.
 */

cbr_CRTable::cbr_CRTable()
{
	sem_init(&crtable_sem, 0, 1);
}

/**
 * CBR routes table destructor.
 */

cbr_CRTable::~cbr_CRTable()
{
	sem_wait(&crtable_sem);
	while (!routes.empty()) {
		delete routes.front();
		routes.pop_front();
	}
	sem_post(&crtable_sem);

	sem_destroy(&crtable_sem);
}

/**
 * Update/add CBR route to CBR routes table.
 *
 * @param triple reference to CBR triple
 * @param forwarder CBR id of the forwarding node
 *
 * Updates/adds route described by the CBR triple @a tr (concept,
 * source and hop count) and the forwarding node id @a forwarder
 * to the CBR routes table.
 */

void cbr_CRTable::update(const cbr_Triple& triple, cbr_ID forwarder)
{
	routes_list::const_iterator i;
	bool updated = false;

	sem_wait(&crtable_sem);
	for (i = routes.begin(); !updated && i != routes.end(); i++)
		updated |= (*i)->update(triple, forwarder);
	if (!updated) {
		cbr_Route *new_route = new cbr_Route(triple, forwarder);
		routes.push_front(new_route);
	}
	sem_post(&crtable_sem);
}

/**
 * Purge CBR routes table.
 *
 * Deletes routes older than CTX_ROUTE_LIFE.
 */

void cbr_CRTable::purge()
{
	routes_list::iterator i, j;

	sem_wait(&crtable_sem);
	for (i = routes.begin(); i != routes.end();) {
		if ((*i)->expires() < sclock()) {
			j = i;
			i++;
			delete (*j);
			routes.erase(j);
		} else {
			i++;
		}
	}
	sem_post(&crtable_sem);
}

/**
 * Get concepts from the routing table.
 *
 * @note uses crtable_sem semaphore
 *
 * @returns concepts set consisting of all concepts from the routing tables
 */

cbr_ConceptsSet cbr_CRTable::getConcepts(void) const
{
	cbr_ConceptsSet tmp;
	routes_list::const_iterator i;

	sem_wait(&crtable_sem);
	for (i = routes.begin(); i != routes.end();) {
		cbr_Concept c = (*i)->getConcept();

		if (tmp.find(c) == tmp.end())
			tmp.insert(c);
	}
	sem_post(&crtable_sem);

	return tmp;
}

/**
 * Match concepts set against the routing table.
 *
 * @param cset concepts set
 *
 * @note uses crtable_sem semaphore
 *
 * @returns 1 when at least one concept from the concept set is in the
 * routing tables, 0 otherwise.
 */

bool cbr_CRTable::match(cbr_ConceptsSet &cset) const
{
	routes_list::const_iterator i;
	int rc = 0;

	sem_wait(&crtable_sem);
	for (i = routes.begin(); i != routes.end();) {
		cbr_Concept c = (*i)->getConcept();
		cbr_ConceptsSet::const_iterator j;

		for (j = cset.begin(); j != cset.end(); j++)
			if (c == (*j)) {
				rc = 1;
				break;
			}
	}
	sem_post(&crtable_sem);

	return rc;
}

/**
 * Gets CBR routes in the form of CBR triples.
 *
 * If the CBR routes table contains multiple entries for the same
 * source/concept pair (obtained from different forwarders) only
 * the pair with the smallest hop count is included in the CBR
 * triples list.
 *
 * Called by CBR::sendHello.
 *
 * @return list of CBR triples.
 */

cbr_TriplesList cbr_CRTable::getAsTriples() const
{
	cbr_TriplesList list;
	typedef std::pair<cbr_ID, const cbr_Route*> src_item;
	std::multimap<cbr_ID, const cbr_Route*> sources;
	std::multimap<cbr_ID, const cbr_Route*>::iterator k;
	routes_list::const_iterator i;

	sem_wait(&crtable_sem);
	for (i = routes.begin(); i != routes.end(); i++) {
		cbr_ID src = (*i)->getSource();
		k = sources.find(src);
		while (k != sources.end() && k->first == src) {
			if (k->second->getConcept() == (*i)->getConcept())
				break;
		}
		if (k != sources.end() && k->first == src
				&& k->second->getConcept()==(*i)->getConcept()){
			if ((*i)->getMetric() < k->second->getMetric()) {
				k->second = *i;
			}
		} else {
			sources.insert(src_item(src, *i));
		}
	}

	for (k = sources.begin(); k != sources.end(); k++)
		list.push_back(k->second->getAsTriple());
	sem_post(&crtable_sem);

	return list;
}

/**
 * Get forwarders list for a given concept.
 *
 * @param concept concept
 * @param fl list of forwarder id / concept metric pairs
 * @param localID local node ID
 *
 * Gets forwarders list (consisting of forwarder id and hop count pairs)
 * for a given concept.
 *
 * If the CBR routes table contains multiple entries for the same
 * source/concept pair (obtained from different forwarders) only the
 * pair with the smallest hop count is included in the forwarders list.
 *
 * The forwarders list gets updated with the fordwarder id / concept metric
 * pairs for given concept.  If the entry with the identical forwarder id
 * already exists (currently it can happen only for multicast messages)
 * the metric field gets modified iff it is smaller than the previous value.
 *
 * Called by cbr_ContextModel::getForwarders.
 *
 * @return "true" if the forwarder list got modified, "false" otherwise.
 */

bool cbr_CRTable::getForwarders(const cbr_Concept& concept,
			        std::list< std::pair<cbr_ID, int> >& fl,
				cbr_ID localID) const
{
	std::list< std::pair<cbr_ID, int> >::iterator j;
	typedef std::pair<cbr_ID, const cbr_Route*> dest_item;
	std::map<cbr_ID, const cbr_Route*> destinations;
	bool modified = false;
	routes_list::const_iterator i;
	std::map<cbr_ID, const cbr_Route*>::iterator k;

	sem_wait(&crtable_sem);
	for (i = routes.begin(); i != routes.end(); i++) {
		if ((*i)->matches(concept)) {
			cbr_ID src = (*i)->getSource();
			if (src == localID)
				continue;

			k = destinations.find(src);
			if (k == destinations.end()) {
				destinations.insert(dest_item(src,*i));
			} else if ((*i)->getMetric()< k->second->getMetric()) {
				k->second = *i;
			}
		}
	}

	for (k = destinations.begin(); k != destinations.end(); k++) {
		cbr_ID fwd = k->second->getForwarder();
		int metric = k->second->getMetric();

		for (j = fl.begin(); j != fl.end(); j++) {
			if (j->first == fwd)
				break;
		}
		if (j == fl.end()) {
			fl.push_front(std::pair<cbr_ID, int>(fwd, metric));
			modified = true;
		} else if (j->second > metric) {
			j->second = metric;
			modified = true;
		}
	}
	sem_post(&crtable_sem);

	return modified;
}

/**
 * Get forwarders list for a given a node ID.
 *
 * @param id source id
 * @param fl list of forwarder id / concept metric pairs
 * @param localID local node ID
 *
 * Gets forwarders list (consisting of forwarder id and hop count pairs)
 * for a given source id.
 *
 * If the CBR routes table contains multiple entries for the same
 * source id (obtained from different sources) all entries are
 * included in the forwarders list.
 *
 * The forwarders list gets updated with the fordwarder id / concept metric
 * pairs for given source id.  If the entry with the identical forwarder id
 * already exists (currently it can happen only for multicast messages)
 * the metric field gets modified iff it is smaller than the previous value.
 *
 * Called by CBR::forward_rreq_with_restrictions().
 *
 * @return "true" if the forwarder list got modified, "false" otherwise.
 */

bool cbr_CRTable::getForwarders(cbr_ID id,
			        std::list< std::pair<cbr_ID, int> >& fl,
				cbr_ID localID) const
{
	std::list< std::pair<cbr_ID, int> >::iterator j;
	typedef std::pair<cbr_ID, const cbr_Route*> dest_item;
	std::map<cbr_ID, const cbr_Route*> destinations;
	bool modified = false;
	routes_list::const_iterator i;
	std::map<cbr_ID, const cbr_Route*>::iterator k;

	sem_wait(&crtable_sem);
	for (i = routes.begin(); i != routes.end(); i++) {
		cbr_ID src = (*i)->getSource();

		if (src == localID)
			continue;

		if (src == id) {
			k = destinations.find(src);
			if (k == destinations.end()) {
				destinations.insert(dest_item(src,*i));
			} else if ((*i)->getMetric()< k->second->getMetric()) {
				k->second = *i;
			}
		}
	}

	for (k = destinations.begin(); k != destinations.end(); k++) {
		cbr_ID fwd = k->second->getForwarder();
		int metric = k->second->getMetric();

		for (j = fl.begin(); j != fl.end(); j++) {
			if (j->first == fwd)
				break;
		}
		if (j == fl.end()) {
			fl.push_front(std::pair<cbr_ID, int>(fwd, metric));
			modified = true;
		} else if (j->second > metric) {
			j->second = metric;
			modified = true;
		}
	}
	sem_post(&crtable_sem);

	return modified;
}

/**
 * Get sources list for a given concept.
 *
 * @param concept concept
 * @param sl list of source id / concept metric pairs
 * @param localID local node ID
 *
 * Gets sources list for a given concept.
 *
 * If the CBR routes table contains multiple entries for the same
 * concept (obtained from different sources) all entries are
 * included in the forwarders list.
 *
 * Called by cbr_ContextModel::getSources.
 *
 * @return "true" if the sources list got modified, "false" otherwise.
 */

bool cbr_CRTable::getSources(const cbr_Concept& concept,
			    std::list< std::pair<cbr_ID, int> >& sl,
			    cbr_ID localID) const
{
	std::list< std::pair<cbr_ID, int> >::iterator j;
	bool modified = false;
	routes_list::const_iterator i;

	sem_wait(&crtable_sem);
	for (i = routes.begin(); i != routes.end(); i++) {
		if ((*i)->matches(concept)) {
			cbr_ID src = (*i)->getSource();
			int metric = (*i)->getMetric();

			if (src == localID)
				continue;

			for (j = sl.begin(); j != sl.end(); j++) {
				if (j->first == src)
					break;
			}
			if (j == sl.end()) {
				sl.push_front(std::pair<cbr_ID, int>(src, metric));
				modified = true;
			}
		}
	}
	sem_post(&crtable_sem);

	return modified;
}
